package com.cn.why.springcloudskills.FaceTest;

import java.util.ArrayList;
import java.util.List;

/**
 * 自建二叉树
 */
public class MyBinTree {
    private static String[] arr = {"1","2","3","4","5","6","7","8","9","10"};
    private static List<Node> listNode;

    /**
     *成员内部类
     */
    private static class Node{
        String strs = null;
        Node leftNode = null;
        Node right = null;
        public Node(String strs){
            this.strs = strs;
        }
    }

    /**
     * 构建二叉树
     */
    public static void creadBinTree(){
        listNode = new ArrayList<Node>();
        //把数组的值添加到节点
        for (int a = 0;a<arr.length;a++){
            listNode.add(new Node(arr[a]));
        }
        //构建二叉树结构
        int midem = arr.length / 2 - 1;//首先判断该二叉树节点是偶数还是奇数
        for (int b = 0;b<midem;b++){
            //构建左节点
            listNode.get(b).leftNode = listNode.get(b*2+1);
            //构建右节点
            listNode.get(b).right = listNode.get(b*2+2);
        }
        //因为娶不到arr.length - 1，所以单独构建
        listNode.get(midem).leftNode = listNode.get(midem*2+1);
        //此时要判断有没有右节点，则需要判断是不是奇数
        if(midem % 2 == 1){
            listNode.get(midem).leftNode = listNode.get(midem*2+2);
        }
    }

    /**
     * 先序遍历
     * @param root
     */
    private static void leftSort(Node root){
        if(root == null){
            return;
        }
        System.out.print(root.strs+" ");
        leftSort(root.leftNode);
        leftSort(root.right);
    }

    /**
     * 中序遍历
     * @param root
     */
    private static void midelSort(Node root){
        if(root == null){
            return;
        }
        midelSort(root.leftNode);
        System.out.print(root.strs+" ");
        midelSort(root.right);
    }

    /**
     * 后序遍历
     * @param root
     */
    private static void rightSort(Node root){
        if(root == null){
            return;
        }
        rightSort(root.leftNode);
        rightSort(root.right);
        System.out.print(root.strs+" ");
    }

    public static void main(String[] args) {
        MyBinTree.creadBinTree();//创建二叉树结构
        Node root = listNode.get(0);//获得二叉树结构

        //开始遍历
        leftSort(root);
        System.out.println();
        midelSort(root);
        System.out.println();
        rightSort(root);
    }
}
